package 剑指offer;

import java.util.Arrays;
import java.util.LinkedList;

public class 字符串的排列 {

    LinkedList<LinkedList> lists = new LinkedList<>();
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        LinkedList<Character> list = new LinkedList<>();
        boolean[] booleans = new boolean[chars.length];
        if (chars.length==0)
            return new String[0];
        Arrays.sort(chars);
        dfs(chars,list,booleans);
        String[] strings = new String[lists.size()];
        for (int i = 0; i < lists.size(); i++) {
            LinkedList linkedList = lists.get(i);
            String  res = "";
            for (int j = 0; j < linkedList.size(); j++) {
                res+=linkedList.get(j);
            }
            strings[i]=res;
        }
        return strings;
    }

    private void dfs(char[] chars, LinkedList<Character> list, boolean[] booleans) {
        if (list.size()==chars.length)
            lists.add(new LinkedList<>(list));
        for (int i = 0; i < chars.length; i++) {
            if (i>0 && chars[i-1]==chars[i] && !booleans[i-1])
                continue;
            if (!booleans[i]) {
                booleans[i]=true;
                list.add(chars[i]);
                dfs(chars, list, booleans);
                booleans[i]=false;
                list.remove(list.size() - 1);
            }
        }
    }
}
